#pragma once

#include<iostream>
#include<cassert>

namespace Tree {


	enum Color { RED, BLACK };

	template<class K, class V>
	struct RBTreeNode {
		RBTreeNode<K, V>* _left;
		RBTreeNode<K, V>* _right;
		RBTreeNode<K, V>* _parent;


		K _key;
		V _value;

		Color _color;

		RBTreeNode(const K& key = K(), const V& value = V())
			:_key(key), _value(value), _left(nullptr),
			_right(nullptr), _color(RED), _parent(nullptr) {
		}

	};

	template<class K, class V, class Ref, class Ptr >
	struct SetIterator {
		typedef RBTreeNode<K, V> Node;
		typedef SetIterator<K, V, Ref, Ptr> Self;

		Node* _it;
		SetIterator(Node* it = nullptr,Node* root = nullptr):_it(it),_root(root)
		{}

		bool operator==(const Self& it) const
		{
			return _it == it._it;
		}
		bool operator!=(const Self& it) const 
		{
			return _it != it._it;
		}

		Ref operator*() const 
		{
			return _it->_value;
		}
		Ptr operator->() const 
		{
			return &(_it->_value);
		}

		Self& operator++() 
		{
			Node* cur = _it;
			if (_it->_right != nullptr)
			{
				cur = cur->_right;
				while (cur->_left)
				{
					cur = cur->_left;
				}
				_it = cur;

			}
			else
			{
				Node* parent = cur->_parent;
				while (parent && parent->_right == cur)
				{
					cur = parent;
					parent = parent->_parent;
				}
				_it = parent;
			}
			return *this;
		}
		Self operator++(int) 
		{
			Node* cur = _it;
			Node* ret = _it;

			if (_it->_right != nullptr)
			{
				cur = cur->_right;
				while (cur->_left)
				{
					cur = cur->_left;
				}
				_it = cur;

			}
			else
			{
				Node* parent = cur->_parent;
				while (parent && parent->_right == cur)
				{
					cur = parent;
					parent = parent->_parent;
				}
				_it = parent;
			}
			return Self(ret);
		}

		Self& operator--()
		{
			Node* cur = _it;
			if (_it == nullptr)
			{
				Node* rightmost = _root;
				while (rightmost->_right)
				{
					rightmost = rightmost->_right;
				}
				_it = rightmost;
				return *this;
			}

			if (_it->_left != nullptr)
			{
				cur = cur->_left;
				while (cur->_right)
				{
					cur = cur->_right;
				}
				_it = cur;

			}
			else
			{
				Node* parent = cur->_parent;
				while (parent && parent->_left == cur)
				{
					cur = parent;
					parent = parent->_parent;
				}
				_it = parent;
			}
			return *this;
		}
		Self operator--(int)
		{
			Node* cur = _it;
			Node* ret = _it;
			if (_it == nullptr)
			{
				Node* rightmost = _root;
				while (rightmost->_right)
				{
					rightmost = rightmost->_right;
				}
				_it = rightmost;
			}
			else if (_it->_left != nullptr)
			{
				cur = cur->_left;
				while (cur->_right)
				{
					cur = cur->_right;
				}
				_it = cur;

			}
			else
			{
				Node* parent = cur->_parent;
				while (parent && parent->_left == cur)
				{
					cur = parent;
					parent = parent->_parent;
				}
				_it = parent;
			}
			return Self(ret);
		}
		private:
		 Node* _root = nullptr;

	};

	template <class Iterator, class Ref, class Ptr>
	class reverse_Iterator {

		typedef reverse_Iterator<Iterator, Ref, Ptr> Self;
		Iterator _reit;
	public:
		reverse_Iterator(const Iterator& it = Iterator()) :_reit(it)
		{
		}
		Self& operator++()
		{
			--_reit;
			return *this;
		}

		Self operator++(int)
		{
			return _reit--;
		}

		Self& operator--()
		{
			 ++_reit;
			 return *this;
		}

		Self operator--(int)
		{
			return _reit++;
		}

		Ref operator*()
		{
			Iterator tmp = _reit;
			return *(--tmp);
		}

		Ptr operator->()
		{
			Iterator tmp = _reit;
			tmp--;
			return tmp.operator->();
		}

		bool operator==(const Self& it) const
		{
			return _reit == it._reit;
		}
		bool operator!=(const Self& it) const
		{
			return _reit != it._reit;
		}

	};
	using namespace std;

	template<class K, class V, class keyOfvalue>
	class RBTree {
		typedef RBTreeNode<K, V> Node;

	public:
		typedef SetIterator<K, V, V&, V*> Iterator;
		typedef SetIterator<K, V, const V&, const V*> const_Iterator;
		typedef reverse_Iterator<Iterator, V&, V*> reverseIterator;
		typedef reverse_Iterator<const_Iterator, const V&, const V*> const_reverse_Iterator;


		RBTree() :_root(nullptr) {}
		RBTree(const RBTree& tree)
		{
			_root = Copy(tree._root);
		}

		RBTree& operator=(const RBTree& tree)
		{
			return BSTree(tree);
		}
		~RBTree()
		{
			Destroy(_root);
			_root = nullptr;
		}

		Iterator Begin()
		{
			Node* leftmost = _root;
			while (leftmost->_left)
			{
				leftmost = leftmost->_left;
			}
			return Iterator(leftmost, _root);
		}

		Iterator End()
		{
			return Iterator(nullptr, _root);
		}

		const_Iterator cBegin()
		{
			Node* leftmost = _root;
			while (leftmost->_left)
			{
				leftmost = leftmost->_left;
			}
			return const_Iterator(leftmost, _root);
		}

		const_Iterator cEnd()
		{
			return const_Iterator(nullptr, _root);
		}

		reverseIterator rBegin()
		{
			return reverseIterator(End());
		}

		reverseIterator rEnd()
		{
			return reverseIterator(Begin());
		}
		
		const_reverse_Iterator crBegin()
		{
	
			return const_reverse_Iterator(cEnd());
		}

		const_reverse_Iterator crEnd()
		{
			return const_reverse_Iterator(cBegin());
		}



		pair<Iterator,bool> Insert(const V& data) {
			Node* newNode = new Node(keyOfvalue()(data), data);
			K key = keyOfvalue()(data);
			if (_root == nullptr) {
				_root = newNode;
			}
			else {
				Node* parent = _root;
				Node* cur = _root;

				while (cur) {
					parent = cur;
					if (key < cur->_key) cur = cur->_left;
					else if (key > cur->_key) cur = cur->_right;
					else return make_pair<Iterator, bool>(Iterator(newNode), false);
				}

				if (key < parent->_key) {
					parent->_left = newNode;
				}
				else {
					parent->_right = newNode;
				}
				newNode->_parent = parent;
				cur = newNode;

				while (parent != nullptr && parent != _root && parent->_color == RED) {
					Node* grandFather = parent->_parent;
					Node* uncle = (parent == grandFather->_left ? grandFather->_right : grandFather->_left);

					if (uncle != nullptr && uncle->_color == RED) {
						parent->_color = uncle->_color = BLACK;
						grandFather->_color = RED;

						cur = grandFather;
						parent = grandFather->_parent;
					}
					else {//(uncle == nullptr || uncle->_color == BLACK)

						if (parent == grandFather->_left) {
							//     g
							//   p   u
							// c
							if (cur == parent->_left) {
								RotateR(grandFather);

								parent->_color = BLACK;
								grandFather->_color = RED;
							}
							//     g
							//   p   u
							//     c
							else {
								RotateLR(grandFather);
								grandFather->_color = RED;
								cur->_color = BLACK;
							}

						}
						else {
							//     g
							//   u   p
							//         c
							if (cur == parent->_right) {
								RotateL(grandFather);
								parent->_color = BLACK;
								grandFather->_color = RED;
							}
							//     g
							//   u   p
							//     c
							else {
								RotateRL(grandFather);
								grandFather->_color = RED;
								cur->_color = BLACK;
							}
						}
						break;
					}
				}

			}

			_root->_color = BLACK;
			_size++;
			return make_pair<Iterator, bool>(Iterator(newNode), true);
		}

		Iterator Find(const K& key)
		{

			Node* cur = _root;
			while (cur)
			{
				if (key < cur->_key) cur = cur->_left;
				else if (key > cur->_key) cur = cur->_right;
				else return Iterator(cur);
			}
			return End();
		}
		const_Iterator Find(const K& key) const
		{

			Node* cur = _root;
			while (cur)
			{
				if (key < cur->_key) cur = cur->_left;
				else if (key > cur->_key) cur = cur->_right;
				else return const_Iterator(cur);
			}
			return cEnd();
		}
		bool Erase(const K& key)
		{
			if (_root == nullptr) return false;
			Node* parent = _root;
			Node* cur = _root;

			while (cur && cur->_key != key) {
				parent = cur;
				if (key < cur->_key) cur = cur->_left;
				else  cur = cur->_right;
			}
			if (cur == nullptr) return false;

			if (cur->_right == nullptr) {
				if (cur == parent->_left) {
					parent->_left = cur->_left;
				}
				else if (cur == parent->_right) {
					parent->_right = cur->_left;
				}
				else if (cur == _root)
				{
					_root = cur->_left;
				}
				else
				{
					assert(false);
				}
				delete cur;
			}
			else if (cur->_left == nullptr) {
				if (cur == parent->_left) {
					parent->_left = cur->_right;
				}
				else if (cur == parent->_right) {
					parent->_right = cur->_right;
				}
				else if (cur == _root)
				{
					_root = cur->_right;
				}
				else
				{
					assert(false);
				}

				delete cur;
			}
			else {
				Node* leftMaxParent = cur;
				Node* leftMax = cur->_left;
				while (leftMax->_right) {
					leftMaxParent = leftMax;
					leftMax = leftMax->_right;
				}
				swap(cur->_key, leftMax->_key);
				swap(cur->_value, leftMax->_value);

				if (leftMax == leftMaxParent->_left) {
					leftMaxParent->_left = leftMax->_left;
				}
				else {
					leftMaxParent->_right = leftMax->_left;
				}

				delete leftMax;
			}


			_size--;
			return true;
		}
		void Clear()
		{
			Destroy(_root);
			_root = nullptr;
		}
		void InOrder()
		{
			_InOrder(_root);
		}
		bool Empty()
		{
			return _root == nullptr;
		}

		bool IsBalance()
		{

			int blackNum = 0;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_color == BLACK)blackNum++;
				cur = cur->_right;
			}
			return _IsBalance(_root, blackNum, 0);
		}
		void swap( RBTree& t)
		{
			std::swap(_root, t._root);
		}
		int size()
		{
			return _size;
		}
	private:
		void Destroy(Node* root)
		{
			if (root == nullptr) return;

			Destroy(root->_left);
			Destroy(root->_right);

			delete root;
			root = nullptr;
		}
		Node* Copy(Node* root)
		{
			if (root == nullptr) return root;

			Node* newnode = new Node(root->_key, root->_value);

			newnode->_left = Copy(root->_left);
			newnode->_right = Copy(root->_right);

			return newnode;
		}
		bool _IsBalance(Node* root, int blackNum, int selfBlackNum)
		{
			if (root == nullptr)
			{
				if (blackNum != selfBlackNum)
				{
					cout << "Black number error, blackNum: " << blackNum << " , selfBlackNum: " << selfBlackNum << endl;
					return false;
				}
				else
				{
					//cout << "blackNum: " << blackNum << " , selfBlackNum: " << selfBlackNum << endl;
					return true;
				}
			}

			if (root->_color == RED && root->_parent->_color == RED)
			{
				cout << "parent and cur is RED, key:" << root->_key << endl;
				return false;
			}

			if (root->_color == BLACK) selfBlackNum++;
			return _IsBalance(root->_left, blackNum, selfBlackNum) && _IsBalance(root->_right, blackNum, selfBlackNum);
		}

		void RotateR(Node* cur)
		{
			Node* parentOfcur = cur->_parent;
			Node* left = cur->_left;


			cur->_left = left->_right;
			if (left->_right)
				left->_right->_parent = cur;
			left->_right = cur;
			cur->_parent = left;
			if (parentOfcur == nullptr)
			{
				_root = left;
				left->_parent = nullptr;
			}
			else
			{

				if (parentOfcur->_left == cur)
				{
					parentOfcur->_left = left;
					left->_parent = parentOfcur;
				}
				else
				{
					parentOfcur->_right = left;
					left->_parent = parentOfcur;
				}
			}


		}

		void RotateL(Node* cur)
		{
			Node* parentOfcur = cur->_parent;
			Node* right = cur->_right;

			cur->_right = right->_left;
			if (right->_left)
				right->_left->_parent = cur;
			right->_left = cur;
			cur->_parent = right;


			if (parentOfcur == nullptr)
			{
				_root = right;
				right->_parent = nullptr;
			}
			else
			{
				if (parentOfcur->_right == cur)
				{
					parentOfcur->_right = right;
					right->_parent = parentOfcur;
				}
				else
				{
					parentOfcur->_left = right;
					right->_parent = parentOfcur;
				}
			}


		}

		void RotateRL(Node* cur)
		{

			Node* parentOfcur = cur->_parent;

			Node* right = cur->_right;
			Node* leftOfright = right->_left;

			RotateR(right);
			RotateL(cur);

		}

		void RotateLR(Node* cur)
		{
			Node* parentOfcur = cur->_parent;

			Node* left = cur->_left;
			Node* rightOfleft = left->_right;

			RotateL(left);
			RotateR(cur);

		}
		void _InOrder(Node* root)
		{
			if (root == nullptr) return;

			_InOrder(root->_left);

			cout << root->_key << ":" << root->_value << endl;

			_InOrder(root->_right);

		}
		Node* _root = nullptr;
		int _size = 0;
	};

}